package unionFind

/*
详情参考：https://zhuanlan.zhihu.com/p/93647900/
并查集：用于解决连通性问题;判断两个元素是否在同一个集合中;将元素合并到同一个集合

合并：将元素合并到一个集合中，或将一个集合合并到另一个集合
查询：查询元素所在集合的代表元素（根节点）
 */

type UnionFind struct {
	// 在未进行路径压缩的情况下，Parent[i]代表的是元素i的父元素
	Parent []int
}

// 初始化，将n个元素进行编号，第i个元素标号为i，初始化时，每个元素的为一个集合，集合中的代表元素(或者说根节点)就是自己
func (u *UnionFind) init(n int)  {
	u.Parent = make([]int, n)
	for i := 0; i < n; i++ {
		u.Parent[i] = i
	}
}

// 查询元素x所在集合的代表元素（或根节点）
// 如果x==u.Parent[x]，表示元素x是其所在集合的代表元素
// 如果x!=u.Parent[x]，表示x不是该集合的代表元素，同样x的父元素也不一定是代表元素，但是可以根据Parent的映射关系递归找到代表元素
// （因为同属于一个集合的两个元素的代表元素一定是相同的,一个集合只有一个代表元素）
func (u *UnionFind) Find(x int) int {
	if x == u.Parent[x] {
		return x
	}
	// 递归找到代表元素
	return u.Find(u.Parent[x])
}

// 判断元素i,j是否在同一个集合中
func (u *UnionFind) IsConnected(i, j int) bool {
	return u.Find(i) == u.Find(j)
}

// 合并
// 将元素i所在集合的代表元素的父元素修改为元素j所在集合的代表元素
func (u *UnionFind) Merge(i, j int) {
	u.Parent[u.Find(i)] = u.Find(j)
}